#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

class SegmentTree {
    struct Node {
        int l, r;
        int value;
        
        int lazy = 0;
    };

    int n;
    vector<Node> v;

public:
    SegmentTree(int n): n(n) {
        v = vector<Node>(4 * n);
        build(1, 1, n);
    }

    /**
     * 初始化线段树，这里初始化为 0 即可
     */
    void build(int current, int l, int r) {
        v[current].l = l;
        v[current].r = r;

        if (l == r) {
            v[current].value = 0;
            return;
        }

        int mid = (l + r) >> 1;

        build(current << 1, l, mid);
        build(current << 1 | 1, mid + 1, r);

        v[current].value = 0;
    }

    /**
     * 查询某个区间的最大值
     */
    int query(int current, int l, int r) {
        // 当前的节点完全被查询区间包含
        if (l <= v[current].l && r >= v[current].r) {
            return v[current].value;
        }

        // 懒惰标记下推
        pushdown(current);

        int mid = (v[current].l + v[current].r) >> 1;

        int maxValue = 0;
        // l <= 左节点的右边界
        if (l <= mid) {
            maxValue = max(maxValue, query(current << 1, l, r));
        }

        // r > 右节点的左边界
        if (r > mid) {
            maxValue = max(maxValue, query(current << 1 | 1, l, r));
        }

        return maxValue;
    }

    /**
     * 更新某个区间的值
     */
    void update(int current, int l, int r, int value) {
         // 当前的节点完全被查询区间包含
        if (l <= v[current].l && r >= v[current].r) {
            v[current].lazy = value;
            v[current].value = value;
            return;
        }

        // 懒惰标记下推
        pushdown(current);

        int mid = (v[current].l + v[current].r) >> 1;

        if (l <= mid) {
            update(current << 1, l, r, value);
        }

        if (r > mid) {
            update(current << 1 | 1, l, r, value);
        }

        // 取左右区间的最大值
        v[current].value = max(v[current << 1].value, v[current << 1 | 1].value);
    }

    void pushdown(int current) {
        if (v[current].lazy == 0) {
            return;
        }
        
        // 将懒惰标记下推给左右子节点，并更新左右子节点的值
        v[current << 1].lazy = v[current].lazy;
        v[current << 1 | 1].lazy = v[current].lazy;

        v[current << 1].value = v[current].lazy;
        v[current << 1 | 1].value = v[current].lazy;

        v[current].lazy = 0;
    }
    
    // void build(int current, int l, int r, vector<int>& nums) {
    //     v[current].l = l;
    //     v[current].r = r;

    //     if (l == r) {
    //         v[current].value = nums[l];
    //         return;
    //     }

    //     int mid = (l + r) >> 1;

    //     build(current * 2, l, mid, nums);
    //     build(current * 2 + 1, mid, r, nums);

    //     v[current].value = v[current * 2].value + v[current * 2 + 1].value;
    // }
};


class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        vector<int> ans;

        // 数据离散化
        vector<int> pos;

        for (int i = 0; i < positions.size(); i++) {
            pos.push_back(positions[i][0]);
            pos.push_back(positions[i][0] + positions[i][1] - 1);
        }

        sort(pos.begin(), pos.end());

        unordered_map<int, int> m;

        int id = 1;
        m[pos[0]] = id;
        
        for (int i = 1; i < pos.size(); i++) {
            if (i == 0 || pos[i] != pos[i - 1]) {
                m[pos[i]] = ++id;
            }
        }

        SegmentTree s(m.size());

        int maxHeight = 0;
        for (int i = 0; i < positions.size(); i++) {
            int l = m[positions[i][0]];
            int r = m[positions[i][0] + positions[i][1] - 1];

            int height = s.query(1, l, r);
            int newHeight = height + positions[i][1];
            s.update(1, l, r, newHeight);

            maxHeight = max(maxHeight, newHeight);
            ans.push_back(maxHeight);
        }

        return ans;
    }
};